package kmp

func FindIndex(originalString string, substring string) int {
	if len(substring) > len(originalString) || substring == "" {
		return -1
	}
	next := GetNext(substring)

	originalNextCompareIndex := 0
	substringNextCompareIndex := 0

	for originalNextCompareIndex < len(originalString) && substringNextCompareIndex < len(substring) {
		if originalString[originalNextCompareIndex] == substring[substringNextCompareIndex] {
			originalNextCompareIndex++
			substringNextCompareIndex++
		} else if next[substringNextCompareIndex] != -1 {
			substringNextCompareIndex = next[substringNextCompareIndex]
		} else {
			originalNextCompareIndex++
		}
	}
	if substringNextCompareIndex == len(substring) {
		return originalNextCompareIndex - substringNextCompareIndex
	}
	return -1
}

func GetNext(match string) []int {
	if len(match) == 1 {
		return []int{-1}
	}
	next := make([]int, len(match))
	next[0] = -1
	next[1] = 0

	nI := 2
	cI := 0
	for nI < len(match) {
		if match[nI-1] == match[cI] {
			next[nI] = cI +1
			nI++
			cI++
		} else if next[cI] != -1 {
			cI = next[cI]
		} else {
			next[nI] = 0
			nI++
		}
	}
	return next
}